#include <iostream>
#define MAXSIZE 1000
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define TURE 1
#define FAULT 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

#define KIND_GT 0
#define KIND_GE 1
#define KIND_LT 2
#define KIND_LE 3
#define KIND_EQ 4
#define KIND_NE 5

#define ElemType int
using namespace std;

typedef int Status;

typedef struct {
    ElemType *elem;
    int length;
    int listsize;
}Sqlist;

void print_list(Sqlist L, int begin=0, int end=0) {
    if (!end) {
        end = L.length;
    }
    if (begin<0 || end > L.length) {
        cout<<"Warning from function print_list: illegal begin or end "<<begin<<" "<<end<<endl;
        return;
    }
    for(int i = begin; i < end; ++i) cout<<"Element "<<i+1<<"==\t"<<L.elem[i]<<endl;
}

Status InitList_Sq(Sqlist &L) {
    L.elem=(ElemType *)malloc (LIST_INIT_SIZE*sizeof(ElemType));
    if(!L.elem) exit(OVERFLOW);
    L.length=0;
    L.listsize=LIST_INIT_SIZE;
    return OK;
}// InitList_Sq

Status ListInsert_Sq(Sqlist &L,int i,ElemType e) {
    if (i<1 || i>L.length+1) {
        cout<<"Waring from function ListInsert_Sq: illegal i\t"<<i<<endl;
        return ERROR;
    }

    if (L.length >= L.listsize) {
        ElemType *newbase;
        newbase = (ElemType *)realloc(L.elem,(LIST_INIT_SIZE + LISTINCREMENT)*sizeof(ElemType));
        if (!newbase) exit(OVERFLOW);
        L.elem = newbase;
        L.listsize += LISTINCREMENT;
    }

    for (int j = L.length; j >= i; j--){
        L.elem[j] = L.elem[j-1];
    }
    L.elem[i-1]=e;

    L.length += 1;
    //cout<<"L.length == "<<L.length<<endl;
    return OK;
} //ListInsert_Sq

Status ListDelete_Sq(Sqlist &L, int i){
    if (i < 1 || i > L.length) {
        cout<<"Warning from function ListDelete: i is illegal\t"<<i<<endl;
        return ERROR;
    }
    for (int j = i-1; j < L.length-1; ++j){
        L.elem[j] = L.elem[j+1];
    }

    --L.length;
    return OK;
}

Status LocateElem_Sq(Sqlist L, ElemType e, int kind) {
    if      (kind == KIND_GT) {for (int i=0; i<L.length; ++i) if (L.elem[i] > e)  return i+1;}
    else if (kind == KIND_GE) {for (int i=0; i<L.length; ++i) if (L.elem[i] >= e) return i+1;}
    else if (kind == KIND_LT) {for (int i=0; i<L.length; ++i) if (L.elem[i] < e)  return i+1;}
    else if (kind == KIND_LE) {for (int i=0; i<L.length; ++i) if (L.elem[i] <= e) return i+1;}
    else if (kind == KIND_EQ) {for (int i=0; i<L.length; ++i) if (L.elem[i] == e) return i+1;}
    else if (kind == KIND_NE) {for (int i=0; i<L.length; ++i) if (L.elem[i] != e) return i+1;}
    else {
        cout<<"Warning from function compare: illegal kind "<<kind<<endl;
        return -1;
    }
    return 0;
}

void MergeList_Sq(Sqlist La, Sqlist Lb, Sqlist &Lc) {
    Lc.listsize = Lc.length = La.length + Lb.length;
    Lc.elem = (ElemType *)realloc(Lc.elem, Lc.listsize*sizeof(ElemType));
    int i = 0, j = 0, k = 0;
    while (i < La.length && j < Lb.length){
        if (La.elem[i] <= Lb.elem[j]) Lc.elem[k++]=La.elem[i++];
        else Lc.elem[k++]=Lb.elem[j++];
    }
    while (i < La.length) Lc.elem[k++] = La.elem[i++];
    while (j < Lb.length) Lc.elem[k++] = Lb.elem[j++];
}

// Begin define the functions of Linklist

typedef struct Lnode{
    ElemType data;
    Lnode *next;
}Lnode, *LinkList;

void print_link(LinkList L, isCircle = 0) {
    LinkList p = L->next;
    int i=0;
    if (isCircle){
        while(++i && p) {
            cout<<"Element "<<i<<"==\t"<<p->data<<endl;
            p = p->next;
        }
    }
    else {
        while(++i && p != L) {
            cout<<"Element "<<i<<"==\t"<<p->data<<endl;
            p = p->next;
        }
    }
}

void CreateList_L(LinkList &L, int n) {
    L = (LinkList) malloc(sizeof(Lnode));
    L->next = NULL;
    LinkList new_one;
    for (int i = n; i > 0; --i) {
        new_one = (LinkList) malloc(sizeof(Lnode));
        cout<<"Please input the\t"<<i<<"th elemnt: "<<endl;
        ElemType e;
        cin>>e;
        new_one->data = e;
        new_one->next = L->next;
        L->next = new_one;
    }
}

Status ListInsert_L(LinkList &L, int i, ElemType e) {
    LinkList p = L;
    int j = 0;
    while (++j < i && p) p = p->next;
    if (j == i) {
        LinkList new_one;
        new_one = (LinkList) malloc(sizeof(Lnode));
        new_one->data = e;
        new_one->next = p->next;
        p->next = new_one;
        return OK;
    }
    else{
        cout<<"Waring from function ListInsert_L: illegal i\tj\t"<<i<<'\t'<<j<<endl;
        return ERROR;
    }
}

Status ListDelete_L(LinkList &L, int i) {
    LinkList p = L;
    int j = 0;
    while (p && j < i-1) {p = p->next;++j;}
    if (j == i-1 && p->next) {
        //cout<<"p->data\t"<<p->data<<endl;
        //cout<<"p->next->data\t"<<p->next->data<<endl;
        //cout<<"p->next->next is \t"<<p->next->next<<endl;
        LinkList q = p->next;
        p->next = p->next->next;
        free(q);
        //print_link(L);
        return OK;
    }
    else {
        cout<<"Waring from function ListDelete_L: illegal i\tj\t"<<i<<'\t'<<j<<endl;
        return ERROR;
    }
}

void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {
    LinkList a = La->next,b = Lb->next;
    Lc = La;
    LinkList c = Lc;
    while (a && b){
        if (b->data < a->data) {
            c->next = b;
            c = b;
            b = b->next;
        }
        else {
            c->next = a;
            c = a;
            a = a->next;
        }
    }
    c->next = a ? a : b;
    free(Lb);
}

// Begin define the function of SLinkList

typedef struct {
    ElemType data;
    int cur;
}component,SLinkList[MAXSIZE];

void print_sl(SLinkList space, int S) {
    int i = 0;
    while (space[S].cur) {
        S = space[S].cur;
        cout<<"Element\t"<<++ i<<"\tis\t"<<space[S].data<<endl;
    }
    cout<<endl;
    //if (i) cout<<"Element\t"<<++ i<<"\tis\t"<<space[S].data<<endl;
}

void InitSpace(SLinkList &space){
    for (int i = 0; i < MAXSIZE-1; ++i) space[i].cur = i+1;
    space[MAXSIZE-1].cur = 0;
}

int Malloc_SL(SLinkList &space) {
    int i;
    i = space[0].cur;
    if (i) space[0].cur = space[i].cur;
    return i;
}

void Free_SL(SLinkList &space, int k) {
    space[k].cur = space[0].cur;
    space[0].cur = k;
}

void difference(SLinkList &space, int &S) {
    InitSpace(space);
    S = Malloc_SL(space);
    int r = S;
    int m, n;
    cout<<"Please input two numbers  you want to deal!  ";
    cin>>m>>n;
    for(int i = 0; i < m; ++i){
        ElemType e;
        cout<<"Input the number for \t"<<i+1<<endl;
        cin>>e;
        int j = Malloc_SL(space);
        space[j].data = e;
        space[r].cur = j;
        r = j;
    }
    space[r].cur = 0;
    cout<<"After Inserted!"<<endl;
    print_sl(space, S);

    for (int i = 0; i < n; ++i) {
        ElemType e;
        cout<<"Input the number for \t"<<i+1<<endl;
        cin>>e;
        int k = S;
        int k_before = 0;
        int counter = 0;
        bool isExisted = 0;
        while (space[k].cur) {
            k_before = k;
            k = space[k].cur;
            if (space[k].data == e) {isExisted = 1;break;};
        }
        if (!isExisted ) {
            cout<<"will add"<<endl;
            int j = Malloc_SL(space);
            space[j].data = e;
            space[j].cur = 0;
            space[k].cur = j;
        }
        else{
            cout<<"will delete"<<endl;
            space[k_before].cur = space[k].cur;
        }
        print_sl(space, S);
    }
}

int main(){
    // Begin Test the Sqlist

    Sqlist La, Lb, Lc;
    InitList_Sq(La);
    //InitList_Sq(Lb);
    //InitList_Sq(Lc);
    ListInsert_Sq(La,1,9);
    ListInsert_Sq(La,2,12);
    ListInsert_Sq(La,3,30);
    ListInsert_Sq(La,4,110);
    //ListInsert_Sq(Lb,1,12);
    //ListInsert_Sq(Lb,2,28);
    //ListInsert_Sq(Lb,3,74);
    //ListInsert_Sq(Lb,4,109);
    //ListInsert_Sq(Lb,5,111);
    //print_list(L);
    //ListDelete_Sq(L,2);
    //ListDelete_Sq(L,1);
    //cout<<"After delete 2,1..."<<endl;
    //cout<<"Begin print La:"<<endl;
    print_list(La);
    //cout<<"Begin print Lb:"<<endl;
    //print_list(Lb);
    //MergeList_Sq(La, Lb, Lc);
    //cout<<"Begin print Lc:"<<endl;
    //print_list(Lc);
    //int j = 0;
    //if(1 && ++j) ;
    //cout<<j<<endl;
    cout<<"Location(==4)\t"<<LocateElem_Sq(La,4,KIND_EQ)<<endl;
    cout<<"Location(>3)\t"<<LocateElem_Sq(La,3,KIND_GT)<<endl;
    cout<<"Location(<1)\t"<<LocateElem_Sq(La,1,KIND_LT)<<endl;
    cout<<"Location(!=1)\t"<<LocateElem_Sq(La,1,KIND_NE)<<endl;

    // Begin test the Linklist

    //LinkList La, Lb, Lc;
    //CreateList_L(La,5);
    //CreateList_L(Lb,3);
    //ListInsert_L(L, 1, 100);
    //cout<<"There will be a insert warning!"<<endl;
    //ListInsert_L(L, 0, 200);
    //ListInsert_L(L, 1, 10);
    //ListInsert_L(L, 3, 102);
    //ListInsert_L(L, 3, 101);
    //cout<<"La: "<<endl;
    //print_link(La);
    //cout<<"Lb: "<<endl;
    //print_link(Lb);
    //MergeList_L(La, Lb, Lc);
    //cout<<"Lc: "<<endl;
    //print_link(Lc);
    //cout<<"after delete 1"<<endl;
    //ListDelete_L(L, 1);
    //print_link(L);
    //cout<<"after delete 1"<<endl;
    //ListDelete_L(L,1);
    //print_link(L);
    //cout<<"after delete 2"<<endl;
    //ListDelete_L(L,2);
    //print_link(L);
    //cout<<"after delete 1"<<endl;
    //ListDelete_L(L,1);
    //print_link(L);
    //cout<<"There will be a delete warning!"<<endl;
    //ListDelete_L(L,1);

    //Begin Test The SLinkList

    //SLinkList space;
    //int S;
    //space[2].data = 2;
    //space[3].data = 3;
    //space[4].data = 4;
    //space[5].data = 5;
    //space[1].cur = 2;
    //space[2].cur = 4;
    //space[4].cur = 3;
    //space[3].cur = 5;
    //space[5].cur = 0;
    //print_sl(space, 1);
    //difference(space, S);


}


